#ifndef StaticList_h__
#define StaticList_h__

/*
===============================================================================

Static List template
A non-growing, memory_set-able list using no memory allocation.

===============================================================================
*/

namespace inf {

    template<typename Iter>
    int staticListSortCompare_Less( Iter a, Iter b ) {
        return *a - *b;
    }

    template<typename Type, int Dim>
    class StaticList
    {
    public:
        typedef Type        value_type;
        typedef const Type	const_value_type;
        typedef Type*		iterator;
        typedef const_value_type*	const_iterator;

        typedef int		cmp_t( const_iterator , const_iterator );

        StaticList( void );
        StaticList( const StaticList<Type,Dim>& other );
        ~StaticList( void );

        void				clear( void );										// marks the list as empty.  does not deallocate or intialize data.
        int					size( void ) const;									// returns number of elements in list
        int					maxSize( void ) const;									// returns the maximum number of elements in the list
        bool				empty( void ) const;								// returns true if number elements in list is 0

        size_t				total_size( void ) const;									// returns total total_size of overhead memory + allocated memory
        size_t				allocated( void ) const;							// returns total total_size of allocated memory
        size_t				memory_used( void ) const;							// returns total_size of the used elements in the list
        void                ready_num( int n );

        const Type& 		operator[]( int index ) const;
        Type&				operator[]( int index );

        Type*				alloc_to_back( void );								// returns reference to a new data element at the end of the list.  returns NULL when full.
        int					append( const Type & obj );							// append element
        int					append( const StaticList<Type,Dim> &other );		// append list
        int					add_unique( const Type & obj );						// add unique element
        int					insert( const Type & obj, int index );				// insert the element at the given index
        bool				remove_index( int index );							// remove the element at the given index
        bool				remove_index_fast( int index );						// remove the element at the given index and put the last element into its spot
        bool				remove( const Type & obj );							// remove the element
        bool				remove_fast( const Type & obj );						// remove the element, move the last element into its spot

        int					find_index( const Type& obj ) const;				// find the index for the given element
        const Type*		    find_element( const Type& obj ) const;				// find pointer to the given element

        void				swap( StaticList<Type,Dim>& other );				// swap the contents of the lists
        void				sort( cmp_t* compare = staticListSortCompare_Less<const_iterator> );



        // members for compatibility with STL algorithms
        iterator			begin( void );										// return list[ 0 ]
        const_iterator		begin( void ) const;								// return list[ 0 ]

        iterator			end( void );										// return list[ num ]	(one past end)
        const_iterator		end( void ) const;									// return list[ num ]	(one past end)

        Type&				front( void );											// return *list[ 0 ]
        const Type&			front( void ) const;										// return *list[ 0 ]

        Type&				back( void );												// return *list[ num - 1 ]
        const Type&			back( void ) const;										// return *list[ num - 1 ]

        bool				remove( iterator iter );

        template< typename Iter >
        void			fill_from_range( Iter begin, Iter end ) {
            int newNum = (end - begin);
            assert( newNum < Dim );
            num = newNum;
            for( int i = 0; i < num; i++, ++begin ) {
                list[ i ] = *begin;
            }
        }

    protected:
        Type 				list[ Dim ];
        int					num;
    };

    template<typename Type,int Dim>
    StaticList<Type,Dim>::StaticList( void ) {
        num = 0;
    }

    template<typename Type,int Dim>
    StaticList<Type,Dim>::StaticList( const StaticList<Type,Dim> &other ) {
        *this = other;  // this "=" as compile generate
    }

    template<typename Type,int Dim>
    StaticList<Type,Dim>::~StaticList( void ) {
    }

    template< typename Type, int Dim >
    bool StaticList<Type, Dim>::empty( void ) const {
        return num == 0;
    }

    template<typename Type,int Dim>
    void StaticList<Type,Dim>::clear( void ) {
        num	= 0;
    }

    /*
    ================
    Returns the number of elements currently contained in the list.
    ================
    */
    template<typename Type,int Dim>
    int StaticList<Type,Dim>::size( void ) const {
        return num;
    }

    /*
    ================
    StaticList<Type,Dim>::size

    Returns the maximum number of elements in the list.
    ================
    */
    template<typename Type,int Dim>
    int StaticList<Type,Dim>::maxSize( void ) const {
        return Dim;
    }

    template<typename Type,int Dim>
    size_t StaticList<Type,Dim>::allocated( void ) const {
        return Dim * sizeof( Type );
    }

    template<typename Type,int Dim>
    size_t StaticList<Type,Dim>::total_size( void ) const {
        return sizeof( StaticList<Type,Dim> );
    }

    template<typename Type,int Dim>
    size_t StaticList<Type,Dim>::memory_used( void ) const {
        return num * sizeof( list[ 0 ] );
    }

    template<typename Type,int Dim>
    void   StaticList<Type,Dim>::ready_num( int n ) {
        assert( n <= Dim );
        num = n;
    }
    /*
    ================
    Access operator.  Index must be within range or an assert will be issued in debug builds.
    release builds do no range checking.
    ================
    */
    template<typename Type,int Dim>
    const Type &StaticList<Type,Dim>::operator[]( int index ) const {
        assert( index >= 0 );
        assert( index < num );

        return list[ index ];
    }

    /*
    ================
    Access operator.  Index must be within range or an assert will be issued in debug builds.
    release builds do no range checking.
    ================
    */
    template<typename Type,int Dim>
    Type& StaticList<Type,Dim>::operator[]( int index ) {
        assert( index >= 0 );
        assert( index < num );

        return list[ index ];
    }

    /*
    ================
    Returns a pointer to a new data element at the end of the list.
    ================
    */
    template<typename Type,int Dim>
    Type* StaticList<Type,Dim>::alloc_to_back( void ) {
        if ( num >= Dim ) {
            return NULL;
        }

        return &list[ num++ ];
    }

    /*
    ================
    StaticList<Type,Dim>::append

    Increases the Dim of the list by one element and copies the supplied data into it.

    Returns the index of the new element, or -1 when list is full.
    ================
    */
    template<typename Type,int Dim>
    int StaticList<Type,Dim>::append( const Type& obj ) {
        assert( num < Dim );
        if ( num < Dim ) {
            list[ num ] = obj;
            num++;
            return num - 1;
        }

        return -1;
    }


    /*
    ================
    StaticList<Type,Dim>::insert

    Increases the Dim of the list by at leat one element if necessary 
    and inserts the supplied data into it.

    Returns the index of the new element, or -1 when list is full.
    ================
    */
    template<typename Type,int Dim>
    int StaticList<Type,Dim>::insert( const Type& obj, int index ) {
        int i;

        assert( num < Dim );
        if ( num >= Dim ) {
            return -1;
        }

        assert( index >= 0 );
        if ( index < 0 ) {
            index = 0;
        } else if ( index > num ) {
            index = num;
        }

        for( i = num; i > index; --i ) {
            list[i] = list[i-1];
        }

        num++;
        list[index] = obj;
        return index;
    }

    /*
    ================
    StaticList<Type,Dim>::append

    adds the other list to this one

    Returns the Dim of the new combined list
    ================
    */
    template<typename Type,int Dim>
    int StaticList<Type,Dim>::append( const StaticList<Type,Dim> &other ) {
        int i;
        int n = other.size();

        if ( num + n > Dim ) {
            n = Dim - num;
        }
        for( i = 0; i < n; i++ ) {
            list[i + num] = other.list[i];
        }
        num += n;
        return size();
    }

    /*
    ================
    StaticList<Type,Dim>::add_unique

    Adds the data to the list if it doesn't already exist.  Returns the index of the data in the list.
    ================
    */
    template<typename Type,int Dim>
    int StaticList<Type,Dim>::add_unique( const Type& obj ) {
        int index;

        index = find_index( obj );
        if ( index < 0 ) {
            index = append( obj );
        }

        return index;
    }

    /*
    ================
    StaticList<Type,Dim>::find_index

    Searches for the specified data in the list and returns it's index.  Returns -1 if the data is not found.
    ================
    */
    template<typename Type,int Dim>
    int StaticList<Type,Dim>::find_index( const Type& obj ) const {
        int i;

        for( i = 0; i < num; i++ ) {
            if ( list[ i ] == obj ) {
                return i;
            }
        }

        // Not found
        return -1;
    }

    /*
    ================
    StaticList<Type,Dim>::find

    Searches for the specified data in the list and returns it's address. Returns NULL if the data is not found.
    ================
    */
    template<typename Type,int Dim>
    const Type* StaticList<Type,Dim>::find_element( const Type& obj ) const {
        int i;

        i = find_index( obj );
        if ( i >= 0 ) {
            return &list[ i ];
        }

        return NULL;
    }

    /*
    ================
    StaticList<Type,Dim>::remove_index

    Removes the element at the specified index and moves all data following the element down to fill in the gap.
    The number of elements in the list is reduced by one.  Returns false if the index is outside the bounds of the list.
    Note that the element is not destroyed, so any memory used by it may not be freed until the destruction of the list.
    ================
    */
    template<typename Type,int Dim>
    bool StaticList<Type,Dim>::remove_index( int index ) {
        int i;

        assert( index >= 0 );
        assert( index < num );

        if ( ( index < 0 ) || ( index >= num ) ) {
            return false;
        }

        num--;
        for( i = index; i < num; i++ ) {
            list[ i ] = list[ i + 1 ];
        }

        return true;
    }

    /*
    ===============
    StaticList<Type, Dim>::remove_index_fast

    Removes the element at the specified index and moves the last element into
    it's spot, rather than moving the whole array down by one.  Of course, this 
    doesn't maintain the order of elements!
    The number of elements in the list is reduced by one.  Returns false if the 
    index is outside the bounds of the list. Note that the element is not destroyed, 
    so any memory used by it may not be freed until the destruction of the list.
    ===============
    */
    template< typename Type, int Dim >
    bool StaticList< Type, Dim >::remove_index_fast( int index ) {
        assert( index >= 0 );
        assert( index < num );

        if ( ( index < 0 ) || ( index >= num ) ) {
            return false;
        }	

        num--;

        // nothing to do
        if( index == num )  {
            return true;
        }
        list[ index ] = list[ num ];

        return true;
    }

    /*
    ================
    StaticList<Type,Dim>::remove

    Removes the element if it is found within the list and moves all data following the element down to fill in the gap.
    The number of elements in the list is reduced by one.  Returns false if the data is not found in the list.  Note that
    the element is not destroyed, so any memory used by it may not be freed until the destruction of the list.
    ================
    */
    template<typename Type,int Dim>
    bool StaticList<Type,Dim>::remove( const Type& obj ) {
        int index;

        index = find_index( obj );
        if ( index >= 0 ) {
            return remove_index( index );
        }

        return false;
    }

    /*
    ================
    StaticList<Type, Dim>::remove_fast

    Removes the element if it is found within the list and moves the last element into the gap.
    The number of elements in the list is reduced by one.  Returns false if the data is not found in the list.  Note that
    the element is not destroyed, so any memory used by it may not be freed until the destruction of the list.
    ================
    */
    template< typename Type, int Dim >
    bool StaticList<Type, Dim>::remove_fast( const Type& obj ) {
        int index;

        index = find_index( obj );
        if ( index >= 0 ) {
            return remove_index_fast( index );
        }

        return false;
    }

    /*
    ================
    StaticList<Type,Dim>::swap

    Swaps the contents of two lists
    ================
    */
    template<typename Type,int Dim>
    void StaticList<Type,Dim>::swap( StaticList<Type,Dim>& other ) {
        StaticList<Type,Dim> temp = *this;
        *this = other;
        other = temp;
    }

    /*
    ================
    StaticList<Type, Dim>::begin

    Returns the first element of the list
    ================
    */
    template< typename Type, int Dim >
    typename StaticList<Type, Dim>::iterator StaticList<Type, Dim>::begin( void ) {
        if( num == 0 ) {
            return end();
        }
        return list;
    }

    /*
    ================
    StaticList<Type, Dim>::begin(void) const

    Returns the first element of the list
    ================
    */
    template< typename Type, int Dim >
    typename StaticList<Type, Dim>::const_iterator StaticList<Type, Dim>::begin( void ) const {
        if( num == 0 ) {
            return end();
        }
        return list;
    }

    /*
    ================
    StaticList<Type, Dim>::end

    Returns one past the end of the list
    ================
    */
    template< typename Type, int Dim >
    typename StaticList<Type, Dim>::iterator StaticList<Type, Dim>::end( void ) {
        return list + num;
    }


    /*
    ================
    StaticList<Type, Dim>::end(void) const

    Returns one past the end of the list
    ================
    */
    template< typename Type, int Dim >
    typename StaticList<Type, Dim>::const_iterator StaticList<Type, Dim>::end( void ) const {
        return list + num;
    }

    /*
    ================
    StaticList<Type, Dim>::back

    returns the last element
    ================
    */
    template< typename Type, int Dim >
    Type& StaticList<Type, Dim>::back( void ) {
        assert( num != 0 );
        return list[ num - 1 ];
    }

    /*
    ================
    StaticList<Type, Dim>::back(void) const

    returns the last element
    ================
    */
    template< typename Type, int Dim >
    const Type& StaticList<Type, Dim>::back( void ) const {
        assert( num != 0 );
        return list[ num - 1 ];
    }

    /*
    ================
    StaticList<Type, Dim>::front

    returns the first element
    ================
    */
    template< typename Type, int Dim >
    Type& StaticList<Type, Dim>::front( void ) {
        assert( num != 0 );
        return list[ 0 ];
    }

    /*
    ================
    StaticList<Type, Dim>::front(void) const

    returns the first element
    ================
    */
    template< typename Type, int Dim >
    const Type& StaticList<Type, Dim>::front( void ) const {
        assert( num != 0 );
        return list[ 0 ];
    }

    /*
    ================
    StaticList<Type, Dim>::remove
    ================
    */
    template< typename Type, int Dim >
    bool StaticList<Type, Dim>::remove( iterator iter ) {
        int index = iter - list;
        return remove_index( index );
    }

    /*
    ================
    StaticList<Type>::sort

    Performs a qsort on the list using the supplied comparison function.  Note that the data is merely moved around the
    list, so any pointers to data within the list may no longer be valid.
    ================
    */
    template<typename Type,int Dim>
    void StaticList<Type,Dim>::sort( cmp_t *compare ) {
        if ( !list || empty() ) {
            return;
        }

        quick_sort( begin(), end(), compare );
    }


}   // ::inf

#endif // StaticList_h__
